package com.atguigu.distributed.lock.leecode;

import java.util.Random;

/**
 * 这一版的寻找第K大是我最常练习的版本
 */
public class FindKthLargest2 {
    private final static Random random = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
        int[] arr2 = {1, 2, 4, 3, 5, 6, 8, 7, 10, 9};
        FindKthLargest2 findKthLargest2 = new FindKthLargest2();
        int kthLargest3 = findKthLargest2.findKthLargest5(arr, 2);
        System.out.println("res==>" + kthLargest3);

    }

    public int findKthLargest5(int[] arr, int k) {
        int length = arr.length;
        int target = length - k;
        int left = 0;
        int right = length - 1;
        while (true) {
            int privotIndex = partition5(arr, left, right);
            if (privotIndex == target) {
                return arr[privotIndex];
            } else if (privotIndex < target) {
                left = privotIndex + 1;
            } else {
                right = privotIndex - 1;
            }

        }


    }

    private int partition5(int[] arr, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(arr, left, randomIndex);
        int le = left +1;
        int ge = right;
        while (true) {
            while (le <= ge && arr[le] < arr[left]) {
                le++;
            }
            while (le <= ge && arr[ge] > arr[left]) {
                ge--;
            }
            if (le >= ge) {
                break;
            }
            swap(arr, le, ge);
            le++;
            ge--;
        }
        swap(arr, left, ge);
        return ge;
    }


    public int FindKthLargest3(int[] arr, int k) {
        int length = arr.length;
        int target = length - k;
        int left = 0;
        int right = length - 1;

        while (true) {
            int privotIndex = partition3(arr, left, right);
            if (privotIndex == target) {
                return arr[privotIndex];
            } else if (privotIndex > target) {
                right = privotIndex - 1;
            } else {
                left = privotIndex + 1;
            }

        }

    }

    private int partition3(int[] arr, int left, int right) {
//        int randomIndex = left + random.nextInt(right - left + 1);
//        swap(arr, left, randomIndex);
        int pivot = arr[left];
        int le = left + 1;
        int ge = right;
        while (true) {
            while (le <= ge && arr[le] < pivot) {
                le++;
            }
            while (le <= ge && arr[ge] > pivot) {
                ge--;
            }
            if (le >= ge) {
                break;
            }
            swap(arr, le, ge);
            le++;
            ge--;
        }
        swap(arr, left, ge);
        return ge;

    }


    private int partition2(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;
        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++;
            }
            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }
            if (le >= ge) {
                break;
            }
            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);
        return ge;

    }

    //数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        // 第 1 大的数，下标是 len - 1;
        // 第 2 大的数，下标是 len - 2;
        // ...
        // 第 k 大的数，下标是 len - k;
        int len = nums.length;
        int target = len - k;

        int left = 0;
        int right = len - 1;

        while (true) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == target) {
                return nums[pivotIndex];
            } else if (pivotIndex < target) {
                left = pivotIndex + 1;
            } else {
                // pivotIndex > target
                right = pivotIndex - 1;
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);


        // all in nums[left + 1..le) <= pivot;
        // all in nums(ge..right] >= pivot;
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;

        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++;
            }

            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }

            if (le >= ge) {
                break;
            }
            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);
        return ge;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
